package lc.q101_150;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 实现一个LRU cache
 */
public class Q146 {

    // 用一个双向链表
    static class DLinkedNode {
        private int key;
        private int value;
        private DLinkedNode prev;
        private DLinkedNode next;
    }

    private DLinkedNode root;
    private DLinkedNode tail;



    int size;
    int maxSize;

    private HashMap<Integer, DLinkedNode> caches = new HashMap<>();

    public Q146(int cap) {
        this.maxSize = cap;
        // root和tail都设置未空节点
        root = new DLinkedNode();
        tail = new DLinkedNode();
        root.next = tail;
        tail.prev = root;
    }

    private void dropTail() {
        final DLinkedNode prev = tail.prev;
        if (prev != root) {
            dropNode(prev);
        }
    }

    private void dropNode(DLinkedNode node) {
        final DLinkedNode prev = node.prev;
        final DLinkedNode next = node.next;
        prev.next = next;
        next.prev = prev;
        caches.remove(node.key);
    }

    private void addNode(DLinkedNode node) {// 总是加到root后节点
        node.next = root.next;
        node.prev = root;
        root.next.prev = node;
        root.next = node;
        caches.put(node.key, node);
    }

    private void moveToHead(DLinkedNode node) {
        dropNode(node);
        addNode(node);
    }

    public void put(int key, int value) {
        if (!caches.containsKey(key)) {
            if (size >= maxSize) {
                dropTail();
            }
            DLinkedNode dLinkedNode = new DLinkedNode();
            dLinkedNode.key = key;
            dLinkedNode.value = value;
            addNode(dLinkedNode);
            size ++;
        } else {
            final DLinkedNode node = caches.get(key);
            node.value =value;
            moveToHead(node);
        }
    }

    public int get(int key) {
        final DLinkedNode node = caches.get(key);
        if (node == null) {
            return -1;
        } else {
            moveToHead(node);
            return node.value;
        }
    }

    public static void main(String[] args) {
        final Q146 q146 = new Q146(2);
        q146.put(1,1);
        q146.put(2,2);
        final int i = q146.get(1);
        System.out.println(i);
        q146.put(3,3);
        final int i1 = q146.get(2);
        System.out.println(i1);
        q146.put(4,4);
        System.out.println(q146.get(1));
        System.out.println(q146.get(3));
        System.out.println(q146.get(4));
    }


}
